package io.github.hadyang.leetcode.offer;

import java.util.LinkedList;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class IsSymmetrical {
  boolean isSymmetrical(TreeNode pRoot) {
    LinkedList<Integer> scanner = new LinkedList<>();
    LinkedList<Integer> symmetricalScanner = new LinkedList<>();

    preScanner(scanner, pRoot);
    symmetricalPreScanner(symmetricalScanner, pRoot);

    return scanner.equals(symmetricalScanner);
  }

  /**
   * 普通的前序遍历
   *
   * @param res
   * @param root
   */
  private void preScanner(LinkedList<Integer> res, TreeNode root) {
    if (root == null) {
      res.addLast(null);
      return;
    }

    res.addLast(root.val);

    preScanner(res, root.left);
    preScanner(res, root.right);
  }

  /**
   * 先右再左的前序遍历
   *
   * @param res
   * @param root
   */
  private void symmetricalPreScanner(LinkedList<Integer> res, TreeNode root) {
    if (root == null) {
      res.addLast(null);
      return;
    }

    res.addLast(root.val);

    symmetricalPreScanner(res, root.right);
    symmetricalPreScanner(res, root.left);
  }
}
